There are numerous circumstances in which it is useful to determine if a specified path is blocked by a specified obstacle. For example, in robotics, the system may need to find a clear path through a known terrain to a specified destination. This would apply equally well to a fixed position robot with a moveable arm as to a moveable robot. For instance, the outer boundary of a robot arm can be represented by a set of line segments representing the arm's "wire frame", and for any given arm position or future arm position intersection of any of those line segments with a known object indicates that movement of the robot arm to that position would cause a collision.
Other applications include checking an airplane's proposed trajectory against a known terrain and/or set of obstacles, and hidden line calculations for video display systems.
In most circumstances in which path blockage determination is useful, it is also useful to determine a path to get past a particular obstacle. For instance, if it is determined that an airplane's planned route or current heading is blocked by an obstacle, the next problem is to determine a path for avoiding the obstacle. One approach would be to randomly select alternate paths centered around the ordinal path until one is found that does not intersect the obstacle. More constructively, one could attempt to determine a path to an external edge or corner of the obstacle that is closest to the original path and that does not intersect with the obstacle. However, determining that best path using a general purpose computer is too slow for some applications, such as situations where there are dozens, hundreds or even thousands of obstacles to be avoided by a fast moving vehicle.
The present invention provides a fast solution to the question: given a starting point and a destination point in space and an obstacle, what is a good path for getting from the starting point to the destination point while avoiding a collision with the obstacle?
Path blockage analysis is usually accomplished using a general purpose a computer programmed to perform a series of mathematical calculations. In U.S. Pat. No. 4,764,873, dedicated hardware is used to analyze the relationship between a path and an obstacle by converting path and obstacle data into a form suitable for fast analysis and then performing a set of comparisons that sort the path into one of three classes: path obstructed (called a Hit), path clear (called a Miss), or path may be blocked (called Ambiguous). If the initial analysis is ambiguous, U.S. Pat. No. 4,764,873 teaches that the two dimensional path blockage problem can be resolved by performing slope comparison computations. However, for three dimensional path checking problems, the amount of computation required to resolve such ambiguities is considerable. In particular, the technique of the '873 patent to resolve ambiguities for a three-dimensional path is to evaluate a set of planes, one of which contains an object edge and one of the two path end points. Then the second end point of the path is evaluated with respect to which side of this plane the point is situated. In the worst case, ambiguity resolution requires evaluation of one path point with respect to twelve planes, each evaluation requiring computation of the determinant of a 3.times.3 matrix. The sign of the resulting determinant indicates which side of a given plane the point in question is located. When the point has been evaluated with respect to all twelve planes, an additional set of logical conditions have to be tested in order to detect an intersection.
U.S. Pat. No. 5,349,533 improves on U.S. Pat. No. 4,764,873 by providing an apparatus and method for minimizing the number of computations required to resolve three dimensional path blockage determinations that are not resolved by the first stage path analyzer hardware. One aspect of minimizing computations is to use an improved coordinate mapping (or labeling) method that facilitates identification of the minimum number of object planes that need to be checked for intersection by a specified line segment. The number of planes to be checked in the worst case is three and in many cases the number of planes to be checked is one or two. Also, instead of requiring the computation of determinants, U.S. Pat. No. 5,349,533 requires computation of no more than four relatively simple linear equations for each plane to be checked.
The present invention extends the technology of U.S. Pat. No. 5,349,533 to provide a system and method for computing a collision avoidance path in a very small number of computational clock cycles. By using several parallel path analyzer units, the time required to compute a path though a field of many obstacles can be greatly reduced.
It is therefore a primary object of the present invention to provide a collision-avoidance path determination system and method that performs three dimensional path analyses substantially faster than it would take a conventional computer to perform the same analyses.
Another object of the present invention is to provide a blockage avoidance analysis system which simultaneously performs a set of computations for selecting an obstacle avoidance path.